'''
https://leetcode.cn/problems/remove-boxes/
'''
from functools import cache
from typing import List


class Solution:
    def removeBoxes(self, boxes: List[int]) -> int:
        # k: 前边跟着和l位置一样的盒子的个数       从一侧看
        @cache
        def f(l, r, k):
            if l > r:
                return 0
            if l == r:
                return (k + 1) ** 2
            m = l  # [l, m)     范围内都一样
            while m <= r and boxes[m] == boxes[l]:
                m += 1

            cnt = k + m - l
            # ====== 可能性1: 这段区间内[l, m)开始消 和 [m, r]  上考虑
            res = cnt ** 2 + f(m, r, 0)
            # ====== 可能性2，从区间[m, r]与枚举中点，和l端点一样的点. 这里的第一个m端点已经和l端点不一样了
            split = m + 1
            while split <= r:
                if boxes[split] == boxes[l]:
                    res = max(res, f(m, split-1, 0) + f(split, r, cnt))
                split += 1
            return res
        return f(0, len(boxes) - 1, 0)

boxes = [10,8,5,1,9,6,6,9,6,10]
print(Solution().removeBoxes(boxes))